package com.wangp.mywrite.coding;

import org.apache.commons.lang3.tuple.Pair;
import java.util.*;

public class DependencyGraph {
    private Map<String, List<String>> graph;

    public DependencyGraph(List<Pair<String, String>> dependencies) {
        graph = new HashMap<>();
        for (Pair<String, String> dependency : dependencies) {
            String source = dependency.getLeft();
            String target = dependency.getRight();
            List<String> targets = graph.getOrDefault(source, new ArrayList<>());
            targets.add(target);
            graph.put(source, targets);
        }
    }

    public boolean hasCycle(String node) {
        Set<String> visited = new HashSet<>();
        Set<String> onStack = new HashSet<>();
        return dfs(node, visited, onStack);
    }

    private boolean dfs(String node, Set<String> visited, Set<String> onStack) {
        visited.add(node);
        onStack.add(node);
        List<String> neighbors = graph.get(node);
        if (neighbors != null) {
            for (String neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    if (dfs(neighbor, visited, onStack)) {
                        return true;
                    }
                } else if (onStack.contains(neighbor)) {
                    return true;
                }
            }
        }
        onStack.remove(node);
        return false;
    }


    public static void main(String[] args) {
        DependencyGraph dependencyGraph = new DependencyGraph(new ArrayList<Pair<String, String>>() {
            {
                add(Pair.of("A", "B"));
                add(Pair.of("B", "C"));
                add(Pair.of("B", "D"));
                add(Pair.of("D", "A"));
            }
        });
        System.out.println(dependencyGraph.hasCycle("A"));
    }
}